/* The link = http://poj.org/problem?id=1080
 * Another virtual tiger
 */

#include <iostream>
#include <stdio.h>

using namespace std;

const int MAX_SIDE = 85;
int scoringMatrix[MAX_SIDE][MAX_SIDE];

void initialize(void)
{
	scoringMatrix['A']['A'] = 5; 
	scoringMatrix['A']['C'] = -1;
	scoringMatrix['A']['G'] = -2;
	scoringMatrix['A']['T'] = -1;
	scoringMatrix['A']['-'] = -3;

	scoringMatrix['C']['A'] = -1; 
	scoringMatrix['C']['C'] = 5;
	scoringMatrix['C']['G'] = -3;
	scoringMatrix['C']['T'] = -2;
	scoringMatrix['C']['-'] = -4;

	scoringMatrix['G']['A'] = -2; 
	scoringMatrix['G']['C'] = -3;
	scoringMatrix['G']['G'] = 5;
	scoringMatrix['G']['T'] = -2;
	scoringMatrix['G']['-'] = -2;

	scoringMatrix['T']['A'] = -1; 
	scoringMatrix['T']['C'] = -2;
	scoringMatrix['T']['G'] = -2;
	scoringMatrix['T']['T'] = 5;
	scoringMatrix['T']['-'] = -1;

	scoringMatrix['-']['A'] = -3; 
	scoringMatrix['-']['C'] = -4;
	scoringMatrix['-']['G'] = -2;
	scoringMatrix['-']['T'] = -1;
	scoringMatrix['-']['-'] = '*';
}


int main(int argc, char *argv[])
{

	initialize();
	int numberOfTestCases;
	const int MAX_LENGTH_OF_GENE = 101;
	char gene1[MAX_LENGTH_OF_GENE] = {0};
	char gene2[MAX_LENGTH_OF_GENE] = {0};
	scanf("%d", &numberOfTestCases);		

	while (numberOfTestCases > 0)
	{
		int length1, length2;
		gene1[0] = 0;
		gene2[0] = 0;
		scanf("%d %s", &length1, gene1);
		scanf("%d %s", &length2, gene2);

		int **similarity = new int* [length1 + 1];
		for (int i = 0; i < length1 + 1; i++) {
			similarity[i] = new int[length2 + 1];
		}

		similarity[0][0] = 0;
		for (int i = 1; i < length1 + 1; i++) {
			similarity[i][0] = similarity[i - 1][0] + scoringMatrix[gene1[i - 1]]['-'];
		}

		for (int i = 1; i < length2 + 1; i++) {
			similarity[0][i] = similarity[0][i - 1] + scoringMatrix['-'][gene2[i - 1]];
		}

		for (int i = 1; i < length1 + 1; i++) {
			for (int j = 1; j < length2 + 1; j++) {
				similarity[i][j] = max(
					max(similarity[i - 1][j] + scoringMatrix[gene1[i - 1]]['-'] ,
						similarity[i][j - 1] + scoringMatrix['-'][gene2[j - 1]]),
						similarity[i - 1][j - 1] + scoringMatrix[gene1[i - 1]][gene2[j - 1]]);

			}
		}

		printf("%d\n", similarity[length1][length2]);

		--numberOfTestCases;
	}
	return 0;
}